(1) Field of the Invention
The present invention relates to a device that performs a calculation on an elliptic curve, and in particular relates to a device that calculates a scalar-multiplied point that is generated by multiplying a scalar against a point on a Montgomery-type elliptic curve.
(2) Description of the Prior Art
1. Public-Key Encryption
Recently, data communication based on computer technology and communication technology has become widely available, and in this data communication, a secret communication mode or a digital signature mode is used. Here, the secret communication mode is a mode to communicate without leaking communication contents to a person other than the other specified party of the communication. Moreover, the digital signature mode is a mode that shows the correctness of communication contents to the other party of the communication and certifies the identity of the originator.
In the secret communication mode or digital signature mode, an encryption mode called a public-key encryption is used. The public-key encryption is a mode to easily manage encryption keys that are different to each of the other parties of communication when the other parties of communication are many, to be an indispensable fundamental technology to communicate with the many other parties of communication. In the secret communication using the public-key encryption, an encryption key and a decryption key are different, and the decryption key is secret while the encryption key is public.
As a base of security of this public-key encryption, a discrete logarithm problem is used. As for the discrete logarithm problem, there are what is defined on a finite field and what is defined on an elliptic curve as representatives. Moreover, the discrete logarithm problem is described in detail in “A Course in Number theory and Cryptography” by Neal Koblitz, Springer-Verlag, 1987.
2. The Discrete Logarithm Problem on an Elliptic Curve
The discrete logarithm problem on an elliptic curve is described below. Here, p is a prime number and an elliptic curve defined on a finite field GF (p) is E. When we think a set that is obtained by adding a formal point O to the whole points both of x coordinates and y coordinates of which belong to GF (p) among the points on E, this set makes a group with the point O as a zero element. The order of an elliptic curve shows the number of the elements in the above-mentioned set. When G=(gx, gy),−G is defined as −G=(gx,−gy).
The discrete logarithm problem on the elliptic curve is such that, in the case that the elliptic curve E is divisible by a large prime number, element G included in the elliptic curve is a base point. In this case, it is a question that in the case that an integer x that satisfies (Equation 1) Y=x*G to an arbitrary element Y included in the elliptic curve exists, seek x.
Here, p is a prime number and GF (p) is a finite field that has p pieces of element. Additionally, within this patent specification, the symbol * shows calculation to add element included in the elliptic curve plural times, x*G, as the below-mentioned equation shows, means that element G is added x times.x*G=G+G+G+ . . . +G 
A point like x*G is called a scalar-multiplied point.
The reason that this makes the discrete logarithm problem a premise of the security of the public-key encryption is that the above-mentioned problem to the finite field that has many elements is extremely difficult.
3. ElGamal Signature that Applies the Discrete Logarithm Problem on the Elliptic Curve
Hereafter, the digital signature mode by ElGamal signature that applies discrete logarithm problem on the elliptic curve is explained by using FIG. 1.
This figure is a sequence diagram that shows procedures of the digital signature mode by the above-mentioned ElGamal signature. A user A 110, a management center 120 and a user B130 are connected by network. Here, p is a prime number and an elliptic curve defined on a finite field GF (p) is E. Assume that a base point of E is G and the order of E is q. In other words, q is the smallest positive integer to satisfy (Equation 2) q*G=0.
(1) Generation of the Public Keys by the Management Center 120
The management center 120 generates the public key YA of the user A 110, using the secret key xA of the user A 110 that is notified in advance, and complying with the equation 3 (Step S141˜S142). (Equation 3) YA=xA*G
Thereafter, the management center 120 releases the prime number p, the elliptic curve E and the base point G to the public as system parameters, and releases the public key YA of the user A 110 to another user B 130 (Step S143˜S144).
(2) Generation of a Signature by the User A 110
The user A 110 generates a random number k (Step S145). Then, the user A 110 calculates (Equation 4) R1=(rx, ry)=k*G (Step S146) and calculates s from (Equation 5) s×k=m+rx×xA (mod q). Here, m is a message that the user A 110 transmits to the user B 120. Here, × indicates multiplication.
Furthermore, the user A 110 transmits obtained (R1, s) as a signature with the message m to the user B 130 (Step S148).
(3) The Verification of the Signature by the User B 130
The user B 130 confirms the identity of the user A 110 by judging whether (Equation 6) s*R1=m*G+rx*YA is satisfied or not (Step S149). This is obvious because
                                                                        s                *                                  R                  1                                            =                                                {                                                            (                                                                        (                                                      m                            +                                                          rx                              ×                              xA                                                                                )                                                /                        k                                            )                                        ×                    k                                    }                                *                G                                                                                        =                                                (                                      m                    +                                          rx                      ⁢                                                                                          ×                      xA                                                        )                                *                G                                                                                        =                                                m                  *                  G                                +                                                      (                                          rx                      ×                      xA                                        )                                    *                  G                                                                                                        =                                                m                  *                  G                                +                                  rx                  *                  YA                                                                                        (                  Equation          ⁢                                          ⁢          7                )            satisfies.4. Addition of Points on the Elliptic Curve and Calculation Quantity by Double Calculation
In each generation of the public key, the generation of the signature and the verification of the signature in the digital signature mode that is represented above by ElGamal signature that applies the discrete logarithm problem on the elliptic curve, the calculation of scalar multiplication of points on the elliptic curve is carried out. For example, “xA*G” represented in the equation 3, “k*G” represented in the equation 4, “s*R1”, “m*G” and “rx*YA” represented in the equation 6 are the calculation of the scalar multiplication of the points on the elliptic curve.
The calculation formula of the elliptic curve is explained in detail in “Efficient elliptic curve exponentiation” (written by Miyaji, Ono, and Cohen, Advances in cryptology-proceedings of ICICS, 97, Lecture notes in computer science, 1997, Springer-Verlag, 282-290).
Hereafter, the calculation formula of the elliptic curve is explained. Here, the equation of the elliptic curve is y2=x3+ax x+b, the coordinates of an arbitrary point P are (x1, y1) and the coordinates of an arbitrary point Q are (x2, y2). Assume that the coordinates of the point R fixed by R=P+Q are (x3, y3).
In the case of P≠Q, R=P+Q becomes the calculation of addition. The formulae of addition are as follows:
            x      3        =                            {                                    (                                                y                  2                                -                                  y                  1                                            )                        /                          (                                                x                  2                                -                                  x                  1                                            )                                }                2            -              x        1            -              x        2                        y      3        =                            {                                    (                                                y                  2                                -                                  y                  1                                            )                        /                          (                                                x                  2                                -                                  x                  1                                            )                                }                ⁢                  (                                    x              1                        -                          x              3                                )                    -              y        1            
In the case of P=Q, R=P+Q=P+P=2×P is satisfied, and R=P+Q becomes a double calculation.
The formulae of double calculation are as follows:
            x      3        =                            {                                                    (                                                      3                    ⁢                                          x                      1                      2                                                        +                  a                                )                            /              2                        ⁢                          y              1                                }                2            -              2        ⁢                  x          1                                y      3        =                            {                                                    (                                                      3                    ⁢                                          x                      1                      2                                                        +                  a                                )                            /              2                        ⁢                          y              1                                )                ⁢                  (                                    x              1                        -                          x              3                                )                    -              y        1            
Moreover, the above-mentioned calculation is a calculation on the finite field in which elliptic curve is defined. As was represented above, in 2-term coordinates or affine coordinates, namely, the coordinates described until now, in case that addition (hereafter, it is also called “elliptic curve addition”) is performed, every one addition on the elliptic curve needs one inverse number calculation. In general, an inverse number calculation needs about 10 times the calculation quantity as compared with a multiplication on a finite field.
Then, to reduce the calculation quantity, 3-term coordinates called projection coordinates are used. Projection coordinates are coordinates comprising three terms X, Y, Z, in relation to the coordinate (X, Y, Z) and the coordinate (X′, Y′, Z′), a given number n exists and there is a relationship X′=n X, Y′=n Y, Z′=n Z that is satisfied, and (X, Y, Z)=(X′, Y′, Z′) that is satisfied.
An affine coordinate (x, y) and a projection coordinate (X, Y, Z) correspond to each other in the below-mentioned relationship.(x,y)→(x,y,1)(X,Y,Z)→(X/Y,Y/Z) (in the case of Z≠0)
Here, the symbol → is used with the below-mentioned meaning. When an element P1 corresponds to one element in an element P2, the relationship is represented by P1→P2. A zero element O can be represented in the projection coordinates and O=(0, 1, 0).
Hereafter, all the calculations of the elliptic curve are in the projection coordinates. Next, the addition formulae and the double calculation formulae on the projection coordinates are explained. These formulae have, of course, consistency with the addition formulae and the double calculation formulae in the affine coordinates. Exponentiation (scalar multiplication of a point on an elliptic curve) is realized by the repeated calculation of the addition and the double calculation on the elliptic curve. Out of these calculations of scalar multiplication, the calculation quantity of addition does not depend on the parameters of the elliptic curve, but the calculation quantity of the double calculation depends on the parameters of the elliptic curve.
Here, p is a prime number of 160 bits and the elliptic curve is E: y2=x3+ax+b, and when the elements P, Q on the elliptic curve are represented by P=(X1, Y1, Z1) and Q=(X2, Y2, Z2), R=(X3, Y3, Z3)=P+Q is obtained as follows:
(i) in the case of P≠Q
In this case, it is a calculation of an addition.
(Step 1-1) The Calculation of an Intermediate Value
The below-mentioned equations are calculated.U1=X1×Z22  (Equation 8)U2=X2×Z12  (Equation 9)S1=Y1×Z23  (Equation 10)S2=Y2×Z13  (Equation 11)H=U2−U1  (Equation 12)r=S2−S1  (Equation 13)(Step 1-2) The calculation of R=(X3, Y3, Z3)
The below-mentioned equations are calculated.X3=−H3−2×U1×H2+r2  (Equation 14)Y3=−S1×H3+r×(U1×H2−X3)  (Equation 15)Z3=Z1×Z2×H  (Equation 16)(ii) in the case of P=Q (namely, R=2P)
In this case, it is a calculation of double calculation.
(Step 2-1) The calculation of an intermediate value
The below-mentioned equations are calculated.S=4×X1×Y12  (Equation 17)M=3×X12+a×Z14  (Equation 18)T=−2×S+M2  (Equation 19)(Step 2-2) The calculation of R=(X3, Y3, Z3)
The below-mentioned equations are calculated.X3=T  (Equation 20)Y3=−8×Y14+M×(S−T)  (Equation 21)Z3=2×Y1×Z1  (Equation 22)
Next, the calculation quantity in the case of the addition and the double calculation of the elliptic curve are explained. Here, the calculation quantity by one multiplication is represented by 1Mu1, and the calculation quantity by one square multiplication is represented by 1Sq. Moreover, in an ordinary microprocessor, 1Sq ≈0.8Mu1 is satisfied.
According to the above-mentioned examples, the calculation quantity of the addition on the elliptic curve represented in the case of P≠Q is obtained by counting the numbers of the multiplication and the square multiplication in the equations 8˜16 and is 12Mul+4Sq. This is obvious because the calculation quantities of the addition in the equations 8, 9, 10, 11, 14, 15 and 16 are 1Mul+1Sq, 1Mul+1Sq, 2Mul, 2Mul, 2Mul+2Sq, 2Mul and 2Mul, respectively.
Additionally, according to the above-mentioned examples, the calculation quantity of the double calculation on the elliptic curve represented in the case of P=Q is obtained by counting the numbers of the multiplication and the square multiplication in the equations 17˜22 and 4Mul+6Sq. This is obvious because the calculation quantities of the square multiplication in the equations 17, 18, 19, 21 and 22 are 1Mul+1Sq, 1Mul+3Sq, 1Sq, 1Mul+1Sq and 1Mul, respectively.
Moreover, in the above-mentioned counting of the number, for example, since the equation 14H3 can be unfolded to H3=H2×H, the calculation quantity of H3 is assumed to be 1Mul+1Sq, and since the equation 18 Z14 can be unfolded to Z14=(Z12)2, the calculation quantity of Z14 is assumed to be 2Sq.
Moreover, as for the equation 14H21 in the above-mentioned process of calculating H3, H2 is calculated, and therefore the calculation quantity of H2 is not counted again. Additionally, at the time of counting the number of multiplication, the number of multiplication that is carried out by multiplying a certain value by a small value is not counted. Hereafter, the reason is explained. The small values mentioned here are, in the equations 8˜22, the small fixed values that are objects for multiplication and, to be more specific, are the values such as 2, 3, 4, 8 and so forth. These values can be represented in binary with 4 bits at most. On the other hand, the other variable numbers have the value of 160 bits ordinarily.
Generally, in a microprocessor, the multiplication of the multiplier and the multiplicand is carried out by the repetition of the shift of the multiplicand and addition. In other words, for each bit of the multiplier represented in binary, in the case that this bit is 1, in order that the least significant bit of the multiplicand represented in binary matches the position where this bit exists, by shifting the multiplicand, one bit string is obtained. In relation to all the bits of the multiplier, all of at least one bit string obtained by this means are added.
For example, in the multiplication of the multiplier of 160 bits and the multiplicand of 160 bits, the multiplicand of 160 bits is shifted 160 times, 160 bit strings are obtained and the obtained 160 bit strings are added. On the other hand, in the multiplication of the multiplier of 4 bits and the multiplicand of 160 bits, the multiplicand of 160 bits is shifted for 4 times, 4 bit strings are obtained and the obtained 4 bit strings are added.
Since the multiplication is carried out as is represented above, in the case that the multiplication is carried out by multiplying a certain value by a small value, the number of the above-mentioned repetition becomes small. Accordingly, the calculation quantity can be regarded as small, and therefore, it is not counted as the number of the multiplication. As is explained above, in the case of carrying out the double calculation of the elliptic curve, the equation 18 includes the parameter a of the elliptic curve. As the value of this parameter a, for example, when a small value is adopted, the calculation quantity of the double calculation on the elliptic curve can be reduced by 1Mul and becomes 3Mul+6Sq. Moreover, as for the addition, even though the parameter of the elliptic curve is changed, the calculation quantity does not change.
The scalar multiplication on the elliptic curve is carried out as follows.
(Prior Art 1)
Suppose p is a prime number of 160 bits, an elliptic curve on the finite field GF (p) is E, and an arbitrary element on E (GF (p)) is G. Calculate k*G based on these parameters. Here, let binary representation bek=k[159]×2159+ . . . +k[2],×22+k[1]×2+k[0]=[k[159], . . . , k[2],k[1],k[0]] (k[0], . . . , k[159]=0 or 1)Step 1: Suppose c=159 and S=0.Step 2: When k[c]=1, suppose S←S+G.Step 3: Suppose c←c−1.Step 4: When c<0, output S and finish. Other than that, suppose S←S+S and return to Step 2.
Suppose the probability of k[c]=1 is ½, let one elliptic curve addition be EAdd, one elliptic curve double calculation EDob, the above-mentioned calculation quantity is 80×EAdd+160×EDob. Generally, when p and k are a prime number of n bits and an integer of n bits respectively, the calculation quantity is1/2×n×EAdd+n×EDob.
In the above-mentioned scalar multiplication, in the case of calculating (2i)*G(i=1, 2, . . . , 159) in advance and of storing the result in a table, calculation is possible as follows.
(Prior Art 2)
Suppose p is a prime number of 160 bits, an elliptic curve on the finite field GF (p) is E and an arbitrary element on E (GF (p)) is G. Additionally, suppose the coordinate of (2i)*G(i=1, 2, . . . , 159) is calculated in advance. At this time, calculate k*G based on these parameters.
Step 1: Suppose c=159 and S=O.
Step 2: When k[c]=1, suppose S←S+2c*G.
Step 3: Suppose c←c−1.
Step 4: In the case of c<0, output S and finish. Other than that, return to Step 2.
In the above-mentioned method, since an elliptic curve addition is not performed, the calculation quantity is 80×EAdd.
Generally, when p and k are a prime number of n bits and an integer of n bits respectively, the calculation quantity is ½×n×EDob. Like this, since the calculation of (2i)*G is performed in advance, the calculation quantity can be reduced. The prior Art 1 can be used in the scalar multiplication of the base point G of the elliptic curve in 3. Elgamal signature is used because the base point G is a system parameter.
5. A Montgomery-Type Elliptic Curve
The above-mentioned elliptic curve is only the elliptic curve whose equation is y2=x3+a×x+b. This elliptic curve is called a Weierstrass-type. On the other hand, an elliptic curve whose equation is Em: B×y2=x3+A×x2+x is called a Montgomery-type elliptic curve. Take a point G on this elliptic curve Em, when it is point multiplied by n1 and it is point multiplied by n2, represented respectively by n1*G=(X1, Y1, Z1), n2*G=(X2, Y2, Z2) and (n1−n2) *G=(X3′, Y3′, Z3′), seek(n1+n2)*G=(X3, Y3, Z3)=n1*G+n2*G as follows.(i) In the case of n1≠n2 (addition)(Step 1-1) Calculation of Intermediate ValueU1=X1+Z1 U2=X2+Z2 V1=X1−Z1 V2=X2−Z2 (Step 1-2) Calculation of (n1+n2)*G=(X3, Y3, Z3)X3=Z3′×(V1×U2+U1×V2)2 Z3=X3′×(V1×U2−U1×V2)2 (ii) In the case of n1=n2 (double calculation)(Step 2-2) Calculation of Intermediate ValueU1=Z1+Z1 V1=X1−Z1 (Step 2-2) Calculation of (n1+n2)*G=(X3, Y3, Z3)X3=V12×U12 Z3=(4×X1×Z1)×(V12+(A+2)/4×(4×X1×Z1)
When “(A+2)/4” of Step 2-2 is ignored because it is calculable in advance, the calculation quantity is 4×Mul+2×Sq (In the case of Z3′=1, 3×Mul+2×Sq) for addition and 3×Mul+2×Sq for double calculation, respectively. As is stated in 4, the calculation quantity for addition and double calculation of a point on a Weierstrass-type elliptic curve is 12×Mul+4×Sq and 4×Mul+6×Sq, respectively. Consequently, addition and double calculation of the point on a Montgomery-type elliptic curve is faster. Moreover, (−1) multiplication of (X1, Y1, X1) is also (X1, −Y1, Z1) on a Montgomery-type elliptic curve. Additionally, on a Montgomery-type elliptic curve, y coordinate cannot be obtained. A Montgomery-type elliptic curve is described in detail in “Speeding the Pollard and Elliptic Curve Methods of Factorization” (written by P. L. Montgomery, Math. of Comp. 48, 1987, pp. 243-264).
As is described above, a Montgomery-type elliptic curve can perform speed-up calculation. But in addition of n1*G to 2*G, since a coordinate of (n1-n2)*G is required, in scalar multiplication, it is impossible to perform binary unfold on a Montgomery-type elliptic curve like on a Weierstrass-type elliptic curve. For example, in the case of calculating 5*G, since 5=2×2+1, after 2*G is calculated, 2*(2*G)=4*G is calculated and further (4*G)+G is calculated. Whereas, in addition of (2*2*G) to G, the difference between these points, namely, (2×2−1)*G=3*G must be obtained. Consequently, the scalar multiplication method like Prior Art 1 cannot be used.
Therefore, the calculation is performed as follows.
(Prior Art 3)
Let p be a prime number of n bits, E be a Montgomery-type elliptic curve on GF (p) and G be an element of E (GF (p)). Calculate k*G as k=2n−1+K[1]×2n−2+ . . . +K[n−2]×2+k[n−1].
Define S[i] and T[i] as follows.S[i]=(2i+k[1]×2i−1+ . . . +k[i−1]×2+k[i])*G T[i]=S[i]+G Step 1: Suppose i=1 and S[0]=G.Step 2: Calculate T[0]=2*G.Step 3: Judge whether k[i+1]=0 or not, and in the case of k[i+1]=0, do as follows.S[i+1]=2*S[i]T[i+1]=S[i]+T[i]
Other than that, calculate as follows.S[i+1]=S[i]+T[i]T[i+1]=2*T[i]Step 4: Suppose i←i+1Step 5: Judge whether i>n−1 or not, and in the case of i>n−1, output S[n] as k*G. Other than that, return to Step 3.
FIG. 2 is a calculation flowchart that shows the calculation procedures of scalar multiplication in the Prior Art 3 graphically. Here, FIG. 2 shows repetitions of addition and double calculation, from right to left. Moreover, in FIG. 2, solid line arrows show addition on the elliptic curve, dotted line arrows show double calculation on the elliptic curve, the value circled on the arrow shows the order of addition (the total number of addition so far), and the value parenthesized on the arrow shows the order of multiplication (the total number of multiplication so far). For example, the first addition (addition of number 1 circled) shows that 3*G is calculated by the addition of G and 2*G on the elliptic curve. Additionally, the first double calculation (multiplication of number 1 parenthesized) shows that 2*G is calculated by the double calculation against G on the elliptic curve.
By this method, since the difference between the two elements that are the objects of addition (addition elements) is always G (a known quantity), there is no need to calculate the difference, therefore, the calculation quantity is the net time required to perform the addition and the double calculation, namely, n×EAdd+n×EDob.
To be more specific, since G is a known quantity and therefore it is possible to think that Z coordinate is 1, EAdd=3×Mul+2×Sq and EDob=3×Mul+s×Sq. Here, Mul and Sq are quantity of multiplication and square on GF (p), respectively and generally Sq=0.8×Mul. When these equations are substituted, the calculation quantity of Prior Art 3 isn×(3×Mul+2×Sq)+n×(3×Mul+2×Sq)=6×n×Mul+4×n×Sq=46/5×n×Mul.
Here, compared with the Prior Art 2 that calculates (2i)*G in advance (uses a table), the calculation method of the Prior Art 3 is not an algorithm that uses the point of (2i)*G, and therefore, the calculation quantity is not reduced as much as the Prior Art 2 and the merit that calculates (2i)*G in advance is small. Additionally, in the scalar multiplication, there is no method in which calculation of a scalar-multiplied point like (2i)*G in advance is effective. Consequently, a Montgomery-type elliptic curve is high-speed in the method that does not have the table of the scalar-multiplied points like the Prior Art 3. However, but there is a problem that no effective method exists in the case of having the table.
In other words, there is a problem that the conventional scalar multiplication method of the Montgomery-type elliptic curve is not effective in the case of having the table of points multiplied by exponentiation of two for a given point.
Moreover, as is apparent because of the above explanation, in the addition and the double calculation on the Montgomery-type elliptic curve, x coordinate (in the case of a projection coordinates that is a 3-term coordinates, x coordinate and z coordinate) can be obtained, but there is a problem that y coordinate cannot be obtained. Consequently, the conventional scalar multiplication on a Montgomery-type elliptic curve cannot be applied to the elliptic curve encryption that needs y coordinate of a scalar-multiplied point.